package algorthm.systemTraning.graph;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.function.Function;

/**
 * @className: DAG
 * @Description:
 * @Author: wangyifei
 * @Date: 2024/5/10 11:04
 */
public class DAG {
    private static Logger logger = LoggerFactory.getLogger(DAG.class);
    /**
     * DAG 的应用场景
     * 1. jar 的依赖分析。
     * 2. 调度任务中 job 的执行顺序。
     */
    public static void main(String[] args) {

    }

    /**
     * 1. 查询入度为 0 的 node ，遍历这些点，并将这些点相关的 edge 删除掉。
     * 2. 重复上面的步骤
     * @param graph
     * @param action
     */
    public static void traversalGraph1(Graph graph , Function<Node , String> action){
        Deque<Node> deque = new ArrayDeque<>();
        for (Node value : graph.nodes.values()) {
            if(value.in == 0){
                deque.addLast(value);
            }
        }
        Node cur = null ;
        while(!deque.isEmpty()){
            // 查找入读为 0 的 node
            while(null != (cur = deque.pollFirst())){
                graph.nodes.remove(cur.value);
                action.apply(cur);
                if(null == cur.next) continue;
                for (Node node : cur.next) {
                    graph.nodes.get(node.value).in--;
                }
            }
            for (Node value : graph.nodes.values()) {
                if(value.in == 0){
                    deque.addLast(value);
                }
            }
        }
    }

    /**
     * 使用 广度优先遍历 + 使用 Set 去重，解决入度为 > 1 的情况
     *     *
     *    /\
     *   *  *  这样的结构
     * @param graph
     * @param action
     */
    public static void traversalGraph2(Graph graph , Function<Node , String> action){

    }
}
